{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rotate List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rotateRight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #旋转链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头节点 <code>head</code> ，旋转链表，将链表每个节点向右移动&nbsp;<code>k</code><em>&nbsp;</em>个位置。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg\" style=\"width: 450px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5], k = 2\n",
    "<strong>输出：</strong>[4,5,1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/13/roate2.jpg\" style=\"width: 305px; height: 350px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [0,1,2], k = 4\n",
    "<strong>输出：</strong>[2,0,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目在范围 <code>[0, 500]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 2 * 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rotate-list](https://leetcode.cn/problems/rotate-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rotate-list](https://leetcode.cn/problems/rotate-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2', '[0,1,2]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        length = 1\n",
    "        cur = head\n",
    "\n",
    "        while cur.next:\n",
    "            length += 1\n",
    "            cur = cur.next\n",
    "        \n",
    "        k = k % length\n",
    "        cur.next = head\n",
    "\n",
    "        temp = head\n",
    "        for i in range(length - k - 1):\n",
    "            temp = temp.next\n",
    "        \n",
    "        new_head = temp.next\n",
    "        temp.next = None\n",
    "\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        if head == None or head.next == None or k==0:\n",
    "            return head\n",
    "        count = 0\n",
    "        extra = ListNode(0)\n",
    "        extra.next = head\n",
    "        p = extra\n",
    "        while (p.next):\n",
    "            count+=1\n",
    "            p = p.next\n",
    "        if k % count ==0:\n",
    "            return head\n",
    "        step = count - k % count\n",
    "        p.next = extra.next\n",
    "        while (step>0):\n",
    "            p = p.next\n",
    "            step-=1\n",
    "        extra.next = p.next\n",
    "        p.next = None\n",
    "        return extra.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type k: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        p = head\n",
    "        q = None\n",
    "        count = 0\n",
    "        while p != None:\n",
    "            q = p\n",
    "            p = p.next\n",
    "            count += 1\n",
    "        \n",
    "        c = (count - k % count) % count\n",
    "        if c == 0:\n",
    "            return head\n",
    "        q.next = head\n",
    "        p = head\n",
    "        for i in range(c):\n",
    "            q = p\n",
    "            p = p.next\n",
    "        q.next = None\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type k: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return head\n",
    "        \n",
    "        p = head\n",
    "        l = 0\n",
    "        tail = None\n",
    "        while p != None:\n",
    "            l += 1\n",
    "            tail = p\n",
    "            p = p.next\n",
    "\n",
    "        k = k % l\n",
    "\n",
    "        if k == 0:\n",
    "            return head \n",
    "        \n",
    "        p = head\n",
    "        print(l, k)\n",
    "        while l > k + 1:\n",
    "            p = p.next\n",
    "            l -= 1\n",
    "\n",
    "        new_head = p.next\n",
    "        p.next = None\n",
    "        tail.next = head\n",
    "\n",
    "        return new_head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type k: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        l = 1\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            l += 1\n",
    "            cur = cur.next\n",
    "        tail = cur\n",
    "        k = l - k % l\n",
    "        for i in range(k):\n",
    "            tail.next = head\n",
    "            head = head.next\n",
    "            tail = tail.next\n",
    "            tail.next = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        temp=head\n",
    "        leng=1\n",
    "        if head==None:\n",
    "            return []\n",
    "        while head.next!=None:\n",
    "            head=head.next\n",
    "            leng+=1\n",
    "        step=k%leng\n",
    "        if step ==0:\n",
    "            return temp\n",
    "        temp2=temp\n",
    "        for i in range(leng-step-1):\n",
    "            temp2=temp2.next\n",
    "        result=temp2.next\n",
    "        temp2.next=None\n",
    "        head.next=temp\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':\n",
    "        if k == 0 or head is None:\n",
    "            return head\n",
    "        first = ListNode(0)\n",
    "        first.next = head\n",
    "        count = 0\n",
    "        cur = first\n",
    "        while cur.next:\n",
    "            count += 1\n",
    "            cur = cur.next\n",
    "        cur.next = head\n",
    "        num = count - (k % count)\n",
    "        res = first\n",
    "        while num>0:\n",
    "            res = res.next\n",
    "            num -= 1\n",
    "        first.next = res.next\n",
    "        res.next = None\n",
    "        return first.next\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        \n",
    "        old_tail = head\n",
    "        n = 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next\n",
    "            n += 1\n",
    "        old_tail.next = head\n",
    "        new_tail = head\n",
    "        for i in range(n - k % n - 1):\n",
    "            new_tail = new_tail.next\n",
    "        new_head = new_tail.next\n",
    "        new_tail.next = None\n",
    "        \n",
    "        return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head: return head\n",
    "        \n",
    "        node, list_len = head, 0\n",
    "        \n",
    "        while node:\n",
    "            node = node.next\n",
    "            list_len += 1\n",
    "\n",
    "        node, idx = head, 0\n",
    "        k %= list_len\n",
    "        \n",
    "        if k == 0: return head\n",
    "        \n",
    "        while True:\n",
    "            if idx == list_len - k - 1:\n",
    "                ans = node.next\n",
    "                node.next = None\n",
    "                node = ans\n",
    "            elif idx == list_len - 1:\n",
    "                node.next = head\n",
    "                break\n",
    "            else: node = node.next\n",
    "            idx += 1\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        o_head,cnt = head,1\n",
    "        while head.next:\n",
    "            head,cnt = head.next,cnt+1\n",
    "        head.next = o_head\n",
    "\n",
    "        step = cnt - k%cnt-1\n",
    "        while step > 0:\n",
    "            o_head,step = o_head.next,step-1\n",
    "        \n",
    "        new_head,o_head.next = o_head.next,None\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "\n",
    "        len = 0\n",
    "        l = head\n",
    "        while l.next!= None:\n",
    "            len += 1\n",
    "            l = l.next\n",
    "        l.next = head\n",
    "        len+=1\n",
    "        ptr = head\n",
    "        for i in range(0,len-k%len-1):\n",
    "            ptr = ptr.next\n",
    "        head = ptr.next\n",
    "        ptr.next = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        old_tail, n = head, 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next\n",
    "            n += 1\n",
    "        # 成环\n",
    "        old_tail.next = head\n",
    "        # 寻找新的链表结尾\n",
    "        new_tail, new_head = None, head\n",
    "        for _ in range(n - k % n):\n",
    "            new_tail = new_head\n",
    "            new_head = new_head.next\n",
    "        # 断开链接\n",
    "        new_tail.next = None\n",
    "        return new_head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    # def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "    #     if not head:\n",
    "    #         return None\n",
    "    #     if not head.next:\n",
    "    #         return head\n",
    "    #     n = 1\n",
    "    #     old_tail = head\n",
    "    #     while old_tail.next:\n",
    "    #         old_tail = old_tail.next\n",
    "    #         n += 1\n",
    "    #     # cycle\n",
    "    #     old_tail.next = head\n",
    "    #     # find the new head\n",
    "    #     new_tail = head\n",
    "    #     for i in range(n - k % n - 1):\n",
    "    #         new_tail = new_tail.next\n",
    "    #     head = new_tail.next\n",
    "    #     new_tail.next = None\n",
    "\n",
    "    #     return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head \n",
    "        old_tail = head \n",
    "        n = 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next \n",
    "            n += 1\n",
    "        old_tail.next = head \n",
    "        for _ in range(n - k % n - 1):\n",
    "            head = head.next \n",
    "        newHead = head.next \n",
    "        head.next = None \n",
    "        return newHead\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        # base cases\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        \n",
    "        # close the linked list into the ring\n",
    "        old_tail = head\n",
    "        n = 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next\n",
    "            n += 1\n",
    "        old_tail.next = head\n",
    "        \n",
    "        # find new tail : (n - k % n - 1)th node\n",
    "        # and new head : (n - k % n)th node\n",
    "        new_tail = head\n",
    "        for i in range(n - k % n - 1):\n",
    "            new_tail = new_tail.next\n",
    "        new_head = new_tail.next\n",
    "        \n",
    "        # break the ring\n",
    "        new_tail.next = None\n",
    "        \n",
    "        return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\r\n",
    "        if not head or not head.next:\r\n",
    "            return head\r\n",
    "        oldTail = head\r\n",
    "        n = 1\r\n",
    "        # oldTail 指针到最后一个元素/\r\n",
    "        while oldTail.next:\r\n",
    "            oldTail = oldTail.next\r\n",
    "            n += 1\r\n",
    "        # 将旧链表连接成环：\r\n",
    "        oldTail.next = head\r\n",
    "        newTail = head\r\n",
    "        # n - k%n - 1 环形新链表头节点的前一个节点\r\n",
    "        for _ in range(n - k%n - 1):\r\n",
    "            newTail = newTail.next\r\n",
    "        # 新链表的头节点\r\n",
    "        newHead = newTail.next\r\n",
    "        # 将新链表的头尾断开：\r\n",
    "        newTail.next = None\r\n",
    "        return newHead\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if head is None: return head\n",
    "        # 计算长度\n",
    "        length = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            length += 1\n",
    "\n",
    "        if k % length == 0: # 若不移动直接返回\n",
    "            return head\n",
    "        \n",
    "        # 取出旋转链表\n",
    "        length -= k % length\n",
    "        cur = head\n",
    "        while length > 1:\n",
    "            print ('cur loop:  ',cur)\n",
    "            cur = cur.next\n",
    "            length -= 1\n",
    "        \n",
    "        tmp = cur.next\n",
    "        print ('tmp:',tmp)\n",
    "        cur.next = None # head去尾\n",
    "        \n",
    "        # 移动到链表尾部\n",
    "        cur1 = tmp\n",
    "        while cur1 and cur1.next:\n",
    "            cur1 = cur1.next\n",
    "        cur1.next = head\n",
    "\n",
    "        return tmp\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "from multiprocessing import dummy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        return self.rotate_right(head, k)\n",
    "\n",
    "    def rotate_right(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or k <= 0:\n",
    "            return head\n",
    "\n",
    "        def cut(cur: ListNode, k: int) -> ListNode:\n",
    "            while k > 1 and cur.next:\n",
    "                cur = cur.next\n",
    "                k -= 1\n",
    "            next_head = cur.next\n",
    "            cur.next = None\n",
    "            return next_head\n",
    "\n",
    "        length = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "        k = k % length\n",
    "\n",
    "        if k == 0:\n",
    "            return head\n",
    "\n",
    "        second_head = cut(head, length - k)\n",
    "        tail = second_head\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        tail.next = head\n",
    "        return second_head\n",
    "\n",
    "\n",
    "    def rotate_right_one(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        length = 0\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        pre = dummy\n",
    "        fast = dummy.next\n",
    "        tail = dummy\n",
    "        slow = dummy.next\n",
    "        p = dummy\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "\n",
    "        k = k % length\n",
    "        counter = 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        pre = mid = cur = head\n",
    "        size = 0\n",
    "        while cur!=None:\n",
    "            size+=1\n",
    "            cur = cur.next\n",
    "        k = k%size\n",
    "        step = k\n",
    "        cur = head\n",
    "        while cur.next!=None:\n",
    "            cur = cur.next\n",
    "            step-=1\n",
    "            if not step:\n",
    "                if pre != mid:\n",
    "                    pre = mid\n",
    "                mid = cur\n",
    "                step = k\n",
    "            print(pre.val, mid.val, cur.val,step)\n",
    "        step = k-step\n",
    "        while step:\n",
    "            pre = pre.next\n",
    "            step-=1\n",
    "        \n",
    "        cur.next = head\n",
    "        head = pre.next\n",
    "        pre.next = None\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        cur_head = head\n",
    "        nodes = []\n",
    "        while cur_head:\n",
    "            nodes.append(cur_head)\n",
    "            cur_head = cur_head.next\n",
    "        if not nodes:\n",
    "            return head\n",
    "        head_idx = (len(nodes) - k % len(nodes)) % len(nodes)\n",
    "        # for node in nodes:\n",
    "        #     print(node)\n",
    "        pre_idx = (head_idx - 1 + len(nodes)) % len(nodes) \n",
    "        tail = nodes[-1]\n",
    "        tail.next = head\n",
    "        nodes[pre_idx].next = None\n",
    "        return nodes[head_idx]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if k==0 or not head or not head.next:\n",
    "            return head\n",
    "        n = 1\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "        \n",
    "        if (add := n - k % n) == n:\n",
    "            return head\n",
    "        \n",
    "        cur.next = head\n",
    "        while add:\n",
    "            cur = cur.next\n",
    "            add -= 1\n",
    "        \n",
    "        ret = cur.next\n",
    "        cur.next = None\n",
    "        return ret\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return None\n",
    "        length = 0\n",
    "        temp = head\n",
    "        while temp:\n",
    "            length += 1\n",
    "            temp = temp.next\n",
    "        \n",
    "        k %= length\n",
    "        if k == 0:\n",
    "            return head\n",
    "        \n",
    "        left = right = head\n",
    "        for i in range(k):\n",
    "            right = right.next\n",
    "        \n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        \n",
    "        right.next = head\n",
    "        head = left.next\n",
    "        left.next = None\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if k == 0 or not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        cur = head\n",
    "        n = 1\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "\n",
    "        add = n - k % n\n",
    "        if add == n:\n",
    "            return head\n",
    "\n",
    "        cur.next = head\n",
    "        while add:\n",
    "            cur = cur.next\n",
    "            add -= 1\n",
    "        \n",
    "        ret = cur.next\n",
    "        cur.next = None\n",
    "        return ret\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head: return head\n",
    "        nodecount = 0\n",
    "        # 计算节点个数\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            nodecount += 1\n",
    "        # rotatenode : 从右拿几个放在左边\n",
    "        rotatenode = k % nodecount\n",
    "        if rotatenode == 0: return head\n",
    "        tmp = head\n",
    "        right = rightpiece = ListNode()\n",
    "        left = leftpiece = ListNode()\n",
    "        i = 0\n",
    "        while tmp:\n",
    "            i += 1\n",
    "            # 右片前 n - 1个节点\n",
    "            if i < nodecount - rotatenode:\n",
    "                rightpiece.val = tmp.val\n",
    "                rightpiece.next = ListNode()\n",
    "                rightpiece = rightpiece.next\n",
    "                tmp = tmp.next\n",
    "            # 右片最后一个节点\n",
    "            elif i == nodecount - rotatenode:\n",
    "                rightpiece.val = tmp.val\n",
    "                tmp = tmp.next\n",
    "            # 左片前 n - 1个节点\n",
    "            elif i > nodecount - rotatenode and i < nodecount:\n",
    "                leftpiece.val = tmp.val\n",
    "                leftpiece.next = ListNode()\n",
    "                leftpiece = leftpiece.next\n",
    "                tmp = tmp.next\n",
    "            # 左片最后一个节点\n",
    "            else:\n",
    "                leftpiece.val = tmp.val\n",
    "                leftpiece.next = right\n",
    "                tmp = tmp.next\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: list, k: int):\n",
    "        if k ==0 or not head or not head.next:\n",
    "            return head\n",
    "        # print(type(head), head)\n",
    "        org_head = copy.deepcopy(head)\n",
    "        data = []\n",
    "        while head.next:\n",
    "                data.append(head.val)\n",
    "                head = head.next\n",
    "        data.append(head.val)\n",
    "        print(data)\n",
    "        data_length = len(data)\n",
    "        transfer = k%data_length\n",
    "        if transfer == 0:\n",
    "            return org_head\n",
    "        # print('transfer', transfer)\n",
    "        new_data = data[-transfer:] + data[:data_length-transfer]\n",
    "        new_data.reverse()\n",
    "        # print('new_data', new_data)\n",
    "\n",
    "        new_head = ListNode(val=new_data[0])\n",
    "\n",
    "        for n in new_data[1:]:\n",
    "            tmp_node = ListNode(val=n)\n",
    "            tmp_node.next = new_head\n",
    "            new_head = tmp_node\n",
    "        # print(type(new_head), new_head)\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        x=head\n",
    "        count=0\n",
    "        tail=x\n",
    "        while x:\n",
    "            count+=1\n",
    "            tail=x\n",
    "            x=x.next\n",
    "        if count==0: return head\n",
    "        #print('tail=',tail.val)\n",
    "        #print(count)\n",
    "        k=k%count\n",
    "        if k==0 : return head\n",
    "        x=head\n",
    "        last=head\n",
    "        #print(count,k,count-k)\n",
    "        for i in range(count-k):\n",
    "            last=x\n",
    "            x=x.next\n",
    "        #print('head=',head.val)\n",
    "        #print('last=',last.val)\n",
    "\n",
    "        tail.next=head\n",
    "        last.next=None\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        start = head\n",
    "        end = head\n",
    "        list_len = 0\n",
    "        while end:\n",
    "            end = end.next\n",
    "            list_len += 1\n",
    "        \n",
    "        k = k%list_len\n",
    "        end = head\n",
    "\n",
    "        for i in range(k):\n",
    "            end = end.next\n",
    "        \n",
    "        if not end:\n",
    "            return head\n",
    "        \n",
    "        while end.next:\n",
    "            start = start.next\n",
    "            end = end.next\n",
    "        \n",
    "        end.next = head\n",
    "        new_head = start.next\n",
    "        start.next = None\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head or not head.next or k == 0:\n",
    "            return head\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        # 计算链表长度n\n",
    "        n = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            p = p.next\n",
    "            n += 1\n",
    "        # 计算实际旋转次数k\n",
    "        k %= n\n",
    "        # 找到链表的倒数第k+1个节点q\n",
    "        p, q = head, head\n",
    "        # p先走k步\n",
    "        for _ in range(k):\n",
    "            p = p.next\n",
    "        # p和q开始同步走，直到p到达最后一个节点\n",
    "        while p and p.next:\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "        # 当前尾节点连到头节点之前\n",
    "        p.next = head\n",
    "        # 倒数第k个节点变成头节点\n",
    "        dummy.next = q.next\n",
    "        # 倒数第k+1个节点变尾节点\n",
    "        q.next = None\n",
    "        return dummy.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
